Leonid Levin

概述

苏联裔美国计算机科学家（1948–），1973年独立提出了与 Cook 本质上相同的 NP 完全性结果。由于冷战时期东西方学术交流的阻碍，他的工作直到后来才被西方学术界所知。

关键内容

独立发现（1973）

• 在1973年发表论文《Universal sequential search problems》
• 使用了"通用搜索问题"的概念，但核心思想与 Cook 一致
• 由于冷战时期学术交流的阻碍，Cook 和 Levin 互不知晓对方的工作

Cook-Levin 定理

• 该定理以两人的名字共同命名，以表彰他们的独立贡献
• Levin 的表述略有不同，但核心思想一致

后续贡献

• 1986年提出了平均情况复杂度理论（average-case complexity）
• 研究了"典型"输入上的计算难度，补充了最坏情况复杂度的不足

来源

• raw/books/计算机科学/08-cook-np-completeness.md

相关

• Stephen Cook — 独立发现者
• Cook-Levin 定理 — 共同证明
• NP 完全性 — 独立提出
• 平均情况复杂度 — 后续贡献